1. Technical Field
The invention relates to image rendering. More particularly, the invention relates to a method and apparatus for providing simple generalized conservative visibility.
2. Description of the Prior Art
Today, the performance of many generalized software based rendering engines does not meet the needs of designers who are attempting to implement complex scenes.
Limitations of VRML
Many application specific high performance rendering engines achieve high performance rendering by restricting the types of scene interaction. The game Doom, for example, does not allow players to look up at the ceiling or down at the floor. Others, such as the UC Berkeley WalkThru System, rely on compute intensive visibility preprocessing based on static elements in the scene (see S. Teller, Visibility Computations in Densely Occluded Polyhedral Environments, Ph.D. dissertation, University of California at Berkeley, (1992); and S. Teller, C. H. Sequin, Visibility Preprocessing for Interactive Walkthroughs, Computer Graphics (Proc. Siggraph '91) 25, 4, pp. 61-69 (1991)). Applying these techniques in VRML 2.0 viewers, requires placing severe constraints on VRML designers.
The generality of VRML scenes makes devising simple, effective visibility algorithms difficult. VRML 2.0 places few constraints on the scene designers. Consequently, any visibility algorithm must be generalizable. Objects in VRML 2.0 can also be added, removed, and transformed through the use of an external interface (such as Java and JavaScript). This means that no object is truly static. A good visibility algorithm for VRML scenes cannot rely on assumptions about static elements in the scene. Many current VRML viewers rely on third party rendering engines to perform the low level rendering of the objects, limiting the viability of algorithms that use such techniques as polygon splitting or merging. Consequently, algorithms that increase rendering performance must do the majority of their work before the low level rendering calls are performed.
Conservative Visibility
Fundamentally, representing a three dimensional image is a matter of determining which objects are visible from the current viewpoint. Many algorithms use an object or polygon list to determine which object or polygon appears in front of other elements in the scene. The performance of these algorithms is related to the number of elements in the list. Complex scenes can have thousands of objects and millions of polygons. Thus, quickly reducing the number of elements in this list by removing elements that are not visible can greatly improve the rendering performance.
Effective conservative visibility algorithms attempt to cull a large number of elements from the scene quickly. A visibility algorithm is considered conservative if it overestimates the number of visible elements, generating a conservative set instead of an exact set of visible elements (see S. Coorg, S. Teller, A Spatially and Temporally Coherent Object Space Visibility Algorithm, Tech. Re. TM-546, Laboratory for Computer Science, MIT, (1996); and S. Coorg, S. Teller, Temporally Coherent Conservative Visibility, Twelfth Annual ACM Symposium on Computational Geometry (1996)).
A typical conservative visibility algorithm identifies a superset of the visible polygons. The standard rendering subsystem is left with the task of determining the exact rendering of the scene given the reduced set of visible elements. By using this system, the hardware or software optimizations used by the underlying rendering subsystem, such as hardware Z-buffering, are preserved.
The computational time necessary to perform the conservative visibility algorithms must be less than the time necessary to apply the underlying rendering subsystem to the culled elements. Consequently, conservative visibility algorithms are especially useful when they can generate a reasonably tight upper bound on the number of elements in the scene.
It would be advantageous to provide an approach that meets all of the above constraints without requiring computationally expensive initialization routines, intensive precomputation, large amounts of memory, or highly specialized data structures.